from 链表 import Node, LinkedList

"""
===== 2022.02.09 =====
1.可以专门添加一个属性值保存length,就不需要每次用length方法遍历链表获取长度。
2.头节点可以用来保存一些公共信息，比如链表长度等。
"""


class SingleLinkedList(LinkedList):
    """
    单链表
    不带头结点 - 第一个节点和其他节点的插入删除操作不一样
    """

    def insert(self, node_to_insert: Node, node=None):
        """
        在node节点后插入一个节点
        在两个节点(P,Q)之间插入一个节点(R)，操作必须注意顺序,不能反： 1.r.next = p.next  2.p.next = r
        """
        cur = self.head
        if self.is_empty:
            self.head = node_to_insert
            print("空链表插入头节点成功")
        else:
            if not node or node not in self.content:
                print("必须选择一个存在链表中的节点")
                return
            while cur != node:
                cur = cur.next_node

            # 执行链表插入操作的标准语句 1.r.next = p.next  2.p.next = r
            node_to_insert.next_node = cur.next_node
            cur.next_node = node_to_insert

            print("{0}节点后插入新节点{1}成功".format(node.node_content, node_to_insert.node_content))

        self.content.append(node_to_insert)

    @property
    def is_empty(self):
        return False if self.head else True

    def remove(self, node):
        """
        删除node节点
        """
        cur = self.head
        if self.is_empty:
            print("空链表无元素可删除")
            return
        tmp_node = None
        while cur != node:
            tmp_node = cur
            cur = cur.next_node
            if cur is None:
                print("元素不存在链表中")
                return
        if cur == self.head:
            self.head = cur.next_node
        else:
            tmp_node.next_node = cur.next_node

        self.content.remove(cur)
        print("删除节点{0}成功".format(node))

    def get_head(self):
        return self.head

    def get_foot(self):
        cur = self.head
        while cur.next_node is not None:
            cur = cur.next_node
        return cur

    @property
    def length(self):
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next_node
        return count

    def get_content(self):
        return [i.node_content for i in self.content if i]

    def get_direction(self):
        cur = self.head
        while cur is not None:
            print("节点名:", cur, " ==> ", "下一节点:", cur.next_node)
            if not cur.next_node:
                break
            cur = cur.next_node

    def add(self, node):
        if self.node_in_list(node):
            return
        node.next_node = self.head
        self.head = node
        self.content.append(node)
        print("链表头添加元素成功")

    def push(self, node):
        if self.node_in_list(node):
            return
        cur = self.head
        if self.is_empty:
            self.head = node
        else:
            while cur.next_node is not None:
                cur = cur.next_node
            cur.next_node = node
        self.content.append(node)
        print("链表尾添加元素成功")

    def search(self, node):
        cur = self.head
        while (cur != node) and (cur.next_node is not None):
            cur = cur.next_node
        if cur == node:
            print("找到节点 %s" % node)
            return cur
        print("节点不在链表中")
        return None

    def node_in_list(self, node):
        cur = self.head
        if not cur:
            return False
        while cur.next_node is not None:
            if cur == node:
                print("error: 节点已存在，不可重复添加")
                return True
            cur = cur.next_node
        return False

    def pop(self):
        if self.is_empty:
            print("空链表无法删除")
            return
        cur = self.head
        if cur.next_node is None:
            print("删除第一个节点成功")
            self.head = None
            self.content.remove(cur)
            return
        tmp_node = cur
        while cur.next_node is not None:
            tmp_node = cur
            cur = cur.next_node
        tmp_node.next_node = None
        self.content.remove(cur)
        print("删除节点{0}成功".format(cur))

    def reverse(self):
        cur = self.head
        while cur:
            self.remove(cur)
            next_node = cur.next_node
            cur = Node(data=cur.data)
            self.add(cur)
            cur = next_node


class HeadSingleLinkedList(SingleLinkedList):
    """
    单链表
    带头结点 - 使得第一个节点和其他节点的插入删除操作一样，简化操作
    """

    def __init__(self):
        super().__init__()
        self.head = Node("头节点")
        self.content.append(self.head)

    def insert(self, node_to_insert: Node, node=None):
        cur = self.head

        if not node or node not in self.content:
            print("必须选择一个存在链表中的节点")
            return
        while cur != node:
            cur = cur.next_node

        # 执行链表插入操作的标准语句 1.r.next = p.next  2.p.next = r
        node_to_insert.next_node = cur.next_node
        cur.next_node = node_to_insert

        self.content.append(node_to_insert)

        print("{0}节点后插入新节点{1}成功".format(node.node_content, node_to_insert.node_content))

    @property
    def is_empty(self):
        return False if self.head.next_node else True

    def get_head(self):
        return self.head

    @property
    def length(self):
        cur = self.head.next_node
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next_node
        return count

    def add(self, node):
        # 表头添加元素等于在头节点后插入一个元素
        self.insert(node, self.head)

    def push(self, node):
        if self.node_in_list(node):
            return
        cur = self.head
        while cur.next_node is not None:
            cur = cur.next_node
        cur.next_node = node
        self.content.append(node)
        print("链表尾添加元素成功")

    def pop(self):
        if self.is_empty:
            print("空链表无法删除")
            return
        cur = self.head
        tmp_node = None
        while cur.next_node is not None:
            tmp_node = cur
            cur = cur.next_node
        tmp_node.next_node = None
        self.content.remove(cur)
        print("删除节点{0}成功".format(cur))

    def remove(self, node):
        cur = self.head
        if self.is_empty:
            print("空链表无元素可删除")
            return
        tmp_node = None
        while cur != node:
            tmp_node = cur
            cur = cur.next_node
            if cur is None:
                print("元素不存在链表中")
                return
        tmp_node.next_node = cur.next_node

        self.content.remove(cur)
        print("删除节点{0}成功".format(node))

    def reverse(self):
        cur = self.head.next_node
        while cur:
            self.remove(cur)
            next_node = cur.next_node
            cur = Node(data=cur.data)
            self.add(cur)
            cur = next_node


if __name__ == '__main__':
    # link_list = SingleLinkedList()
    link_list = HeadSingleLinkedList()
    node1 = Node(data="aaa")
    node2 = Node(data="bbb")
    node3 = Node(data='ccc')
    node4 = Node(data='ddd')
    node5 = Node(data='eee')

    # 空链表是否正常
    print("=== 空链表时 ===")
    print(link_list.get_head())
    link_list.push(node1)
    link_list.pop()
    link_list.push(node1)
    link_list.remove(node1)
    link_list.push(node1)
    link_list.get_direction()

    # 一个节点是否正常
    print("=== 链表一个节点时 ===")
    print(link_list.get_head())
    link_list.push(node3)
    link_list.get_direction()
    link_list.pop()
    link_list.get_direction()
    link_list.push(node3)
    link_list.remove(node3)
    link_list.insert(node3, node1)

    # 两个节点是否正常
    print("=== 链表两个节点时 ===")
    print(link_list.get_head())
    link_list.push(node2)
    link_list.get_direction()
    link_list.pop()
    link_list.insert(node2, node1)
    print(link_list.get_direction())

    # 处理头尾节点是否正常
    print("=== 处理头尾节点 ===")

    # 头节点后插入一个
    link_list.insert(node4, node1)
    link_list.search(node2)
    print(link_list.get_foot())

    # 删除头节点
    link_list.remove(node1)
    print(link_list.get_content())
    link_list.get_direction()

    # 添加尾节点，删除尾节点
    link_list.push(node5)
    link_list.get_direction()
    link_list.remove(node5)
    link_list.get_direction()

    # 逆序
    link_list.reverse()
    link_list.get_direction()
